package pri.zjy.dynamicProgramming;

/**
 * @author zhangjy
 * @description 爬楼梯
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 * <p>
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：n = 2
 * 输出：2
 * 解释：有两种方法可以爬到楼顶。
 * 1. 1 阶 + 1 阶
 * 2. 2 阶
 * 示例 2：
 * <p>
 * 输入：n = 3
 * 输出：3
 * 解释：有三种方法可以爬到楼顶。
 * 1. 1 阶 + 1 阶 + 1 阶
 * 2. 1 阶 + 2 阶
 * 3. 2 阶 + 1 阶
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= n <= 45
 * @date 2025/3/4 15:29
 */
public class ClimbStairs_70 {

    public static void main(String[] args) {
        ClimbStairs_70 climbStairs70 = new ClimbStairs_70();

//        System.out.println(climbStairs70.climbStairs(2));
//        System.out.println(climbStairs70.climbStairs(3));
//        System.out.println(climbStairs70.climbStairs(4));
//        System.out.println(climbStairs70.climbStairs(49));

        System.out.println(climbStairs70.climbStairs4(4));

    }

    /**
     * 个人解法：dp-状态压缩
     * <p>
     * 分析：
     * dp[i]只依赖于前两个值，dp[i - 2] + dp[i - 1]，所以可不用数组维护。
     * 可以通过【状态压缩】优化空间复杂度
     * <p>
     * T(n) = O(n)
     * S(n) = O(1)
     */
    public int climbStairs5(int n) {
        if (n <= 2) return n;

        // 1.dp[i]及i含义
        // dp[i]表示，需要i阶到达楼顶有dp[i]种方式
//        int[] dp = new int[n + 1];

        // 2.递推公式
//        dp[i] = dp[i - 2] + dp[i - 1];

        // 3.初始化
        int num1 = 1, num2 = 2, sum = 0;

        // 4.遍历顺序
        for (int i = 3; i < n + 1; i++) {
            // dp[i] = dp[i - 2] + dp[i - 1];
            // 获取dp[i]
            sum = num1 + num2;
            // 更新num1、num2，分布为i-2、i-1
            num1 = num2;
            num2 = sum;
            // 5.打印
        }

        return sum;
    }

    /**
     * 个人解法：dp
     * <p>
     * T(n) = O(n)
     * S(n) = O(n)
     */
    public int climbStairs4(int n) {
        if (n <= 2) return n;

        // 1.dp[i]及i含义
        // dp[i]表示，需要i阶到达楼顶有dp[i]种方式
        int[] dp = new int[n + 1];

        // 2.递推公式
        // 假设爬第10阶，因为每次只能爬1或2个台阶；那么，要么从第8阶，要么第9阶开始爬。
        // 对于dp[10]，若是第8阶开始爬，则只能选择爬2个台阶这一种方式；若是从第9阶开始爬，则只能选择爬1个台阶这一种方式。
        // 所以，dp[10]=dp[8] + dp[9]
//        dp[i] = dp[i - 2] + dp[i - 1];

        // 3.初始化
        // 为什么没有dp[0]？——因为至少从第 1 阶开始爬；题目告知 n 为正整数，即n=0是异常输入
        dp[1] = 1; // 1
        dp[2] = 2; // 1+1，2

        // 4.遍历顺序
        // 因为dp[i]依赖于前两项，所以遍历的顺序从前到后遍历。
        // 为什么 i=3 开始？——因为，
//        for (int i = 2; i < n + 1; i++) {
        for (int i = 3; i < n + 1; i++) {
            dp[i] = dp[i - 2] + dp[i - 1];
            // 5.打印
            System.out.println("dp[" + i + "]=" + dp[i] + " = " + "dp[" + (i - 2) + "]=" + dp[i - 2] + " + " + "dp[" + (i - 1) + "]=" + dp[i - 1]);
        }

        return dp[n];
    }

    /**
     * 官解：记忆递归 T(n) = O(n) S(n) = O(n)
     * <p>
     * 分析：根据递归，画出其递归树节点，根据递归树可知，普通递归会进行很多重复的运算；
     * 所以，可通过记忆数组memo[]来记录已经计算过的结果，从而保证爬到各级台阶的方法只被记录一次，如
     */
    public int climbStairs3(int n) {
        int memo[] = new int[n + 1];
        return climbStairsMemo(n, memo);
    }

    public int climbStairsMemo(int n, int[] memo) {

        if (memo[n] > 0) return memo[n];

        if (n == 1) {
            memo[n] = 1;
        } else if (n == 2) {
            memo[n] = 2;
        } else {
            memo[n] = climbStairsMemo(n - 1, memo) + climbStairsMemo(n - 2, memo);
        }
        return memo[n];
    }

    // 官方解法：递归（仍然超时） T(n) = O(2^n) S(n) = O(n)
    public int climbStairs2(int n) {

        if (n == 1) return 1;
        if (n == 2) return 2;
        return climbStairs(n - 1) + climbStairs(n - 2);
    }

    // 个人解法：递归-超时
    public int climbStairs(int n) {
        // 爬第0阶也要考虑
        if (n == 0) return 1;
        return climb(1, n - 1) + climb(2, n - 2);
    }

    public int climb(int stairs, int total) {
        // 剩余待爬台阶刚好为0，才算一种
        if (total == 0) return 1;
        // 剩余台阶不够爬
        if (total < 0) return 0;

        int one = climb(1, total - 1);
        int two = climb(2, total - 2);

        return one + two;
    }

}
